\begin{problem}{Расписание на дереве}{p1outtreewc.in}{p1outtreewc.out}{2 секунды}{64 мегабайта}

% Автор условия: Дмитрий Герасимов
% Источник: задачи СПБ ИТМО по теории расписаний

Дан один станок и множество, состоящее из $n$ работ,
причем для каждой работы задано ее время выполнения $p_j$ и вес $w_j$.
Также между работами заданы зависимости такие, что у каждой из некоторых $n-1$ работ зависит ровно от одной другой работы
(для разных работ работы, от которых они зависят, могут различаться), а одна работа~--- не зависит ни от одной.
Таким образом зависимости образуют ориентированное корневое дерево. 

Выполните заданные работы на одном станке.
Необходимо минимизировать взвешенную сумму времен завершения работ $\sum w_j C_j$.

В одно и тоже время на станке не может выполняться более одной работы.
Также нельзя прерываться во время выполнения какой-то работы, нужно выполнять ее до конца.

\InputFile

В первой строке дано целое число $n$ ($1 \le n \le 50\,000$)~--- количество работ.
Во второй строке даны $n$ целых чисел $p_j$ ($1 \le p_j \le 1000$)~--- времена выполения работ.
В третьей строке даны $n$ целых чисел $w_j$ ($1 \le w_j \le 1000$)~--- веса работ.

В следующих $n-1$ строках даны пары целых чисел $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$)~--- пара означает,
что перед выполнением работы $u_i$ необходимо выполнить работу $v_i$.
Гарантируется, что зависимости образуют ориентированное корневое дерево.

\OutputFile

В первой строке выведите целое число~--- оптимальное значение целевой функции.
В следующей строке выведите произвольное оптимальное расписание~--- $n$ целых чисел $t_1, t_2, \cdots, t_n$.
Где $t_i$ --- момент времени, в который нужно начать выполнять $i$-ю работу.

\Examples
\begin{example}%
\exmp{
3
1 3 2
1 6 4
2 1
3 1
}{
49
0 1 4
}%
\exmp{
4
3 4 2 1
2 3 3 2
1 2
4 3
3 2
}{
64
7 0 4 6
}%
\exmp{
7
1 2 3 4 5 6 7
7 6 5 4 3 2 1
2 1
3 1
4 2
5 2
6 3
7 3
}{
210
0 1 3 6 10 15 21 
}%
\end{example}

\Note

В первом примере также оптимально расписание <<0 3 1>>.

\end{problem}
